package leetcode4;

public class Day9 {


    public static void main(String[] args) {
        System.out.println((double) (5/2));

        System.out.println((double) 5/2);

        int[] a = {1,2};
        int[] b = {3,4};
//        findMedianSortedArrays(a,b);
    }


    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //1.预处理数组：保证第一个数组是短的
        if(nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length, n = nums2.length;
        //2.分割线左边元素的个数，后面我们用i表示
        int countLeft = (m + n + 1)/2;
        // 假设nums1数组中分割线右边的下标为i，nums2数组分割线右边的下标为j
        // 分割线左右元素的值满足这个条件：分割线左边的值 都小于等于 分割线右边的值
        //          nums1[i-1]<=nums2[j] nums2[j-1]<=nums1[i] (二分的目的就是找到i和j下标，以该条件为二分条件)

        //3.使用二分查找符合分割线的i,j下标。（暴力解法就是遍历所有的i）
        int left = 0, right = m; //只需要在nums1中进行二分查找即可
        while(left < right) {
            int i = left + (right - left + 1)/2; //nums1数组分割线左边的元素个数，也是分割线右边的第一个元素下标
            int j = countLeft - i;
            if(nums1[i-1] <= nums2[j]) {
                //当前的值可能满足，所以不能+1 . [i,right]
                left = i; //
            }else {
                //当前值是比较大，往左边区间寻找[left,i-1]
                right = i - 1; //为什么-1，因为i这个条件不满足(寻找右端点的二分模版)
            }
        }
        //4.求分割线左右两边的四个值
        int i = left, j = countLeft - i;
        int nums1Left = (i == 0 ? Integer.MAX_VALUE : nums1[i-1]); //i==0说明nums1左边没有值，答案为nums2中的--取最大值是防止取到这个值
        int nums1Right = i == m ? Integer.MIN_VALUE : nums1[i];
        int nums2Left = j == 0 ? Integer.MAX_VALUE : nums2[j-1];
        int nums2Right = j == n ? Integer.MIN_VALUE : nums2[j];

        //5.根据奇偶性返回结果
        if((m + n) % 2 == 0) { //偶数,返回两个数的商
            return (double)(Math.max(nums1Left,nums2Left) + Math.min(nums1Right,nums2Right) / 2);
        }else {
            return (double)Math.max(nums1Left,nums2Left);
        }
    }
}
